package maxProfit;

public class Solution {
    public int maxProfit(int[] prices) {

        // dp[i] 表示前i天时候的最小的价格
        // 找到前i天的最小买价
//        int []dp = new int[prices.length];
//        dp[0] = prices[0];
//        int max = 0; // 最大利润
//        for (int i = 1; i <dp.length ; i++) {
//            dp[i] = Math.min(prices[i],dp[i-1]);
//            max = Math.max(prices[i] - dp[i],max);
//        }
//        return max;
        // dp[i] 表示前i天时候的最低买入价格 如果要在第i天获得最大利润，就要在
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        int max = 0; // 利润
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.min(dp[i-1],prices[i]);
            max = Math.max(prices[i] - dp[i],max);
        }
        return max;
    }
}
// 暴力
//public class Solution {
//    public int maxProfit(int[] prices) {
//        int maxprofit = 0;
//        for (int i = 0; i < prices.length - 1; i++) {
//            for (int j = i + 1; j < prices.length; j++) {
//                int profit = prices[j] - prices[i];
//                if (profit > maxprofit) {
//                    maxprofit = profit;
//                }
//            }
//        }
//        return maxprofit;
//    }
//}